In many computer applications, first data may be represented by a curve traversing two or more dimensions of a multidimensional space, second data may be represented by a point in the same multidimensional space, and it may be useful to determine whether the point representative of the second data lies along the curve representative of the first data. For example, the first data may represent a roadway across the terrain of a geographic region, and the second data may represent an approximate position of a vehicle within that geographic region, perhaps obtained from a global positioning system (GPS) satellite. In such case, it may be useful to determine whether the vehicle is located along the roadway, for example to assess whether the driver of the vehicle should be told either to continue on their way or to correct course.
Furthermore, as the above example suggests, in some applications it may be useful to tolerate some displacement of the point relative to the curve, such that it may be determined that a point which does not lie precisely “on” the curve nevertheless lies “along” the curve. This gives rise to the problem of determining, with a degree of tolerance, whether the point is sufficiently close to the curve to be deemed to be lying “along” the curve. Conventionally, this problem is resolved by measuring the shortest distance between the point and the curve, which involves computing the distance between the point and every point on the curve. This task can be computationally intensive.
There is therefore a need for improvements to methods for determining whether a point lies along a curve in a multidimensional space.